// https://www.lintcode.com/problem/first-missing-positive/

public class Solution {
  /**
    * @param A: An array of integers
    * @return: An integer
    */
  public int firstMissingPositive(int[] A) {
    // write your code here
    int i = 0;
    while (i < A.length) {
      if ((A[i] >= A.length) || (A[i] < 0)) { // 忽略不符合条件的数
        ++i;
      } else if (A[i] != (i + 1)) { // 把数放到正确的位置
        int j = A[i];
        if ((j != 0) && (A[i] != A[j - 1])) { // Python不用操心负数索引，但是Java不行...
          int tmp = A[i];
          A[i] = A[j - 1];
          A[j - 1] = tmp;
        } else {
          ++i;
        }
      } else {
        ++i;
      }
    }
    for (i = 0; i < A.length; ++i) {
      if (A[i] != (i + 1)) {
        return i + 1;
      }
    }
    return A.length + 1;
  }
}